package hotLeetcode;

import java.util.HashMap;

public class H437Leetcode {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    // 哈希表用于存储前缀和的频率
    private HashMap<Integer, Integer> prefixSumMap;

    public int pathSum(TreeNode root, int sum) {
        // 初始化前缀和的哈希表
        prefixSumMap = new HashMap<>();
        // 初始状态，前缀和为0的路径出现过1次
        prefixSumMap.put(0, 1);
        // 从根节点开始递归
        return findPaths(root, sum, 0);
    }

    // 递归查找路径
    private int findPaths(TreeNode node, int target, int currentSum) {
        if (node == null) {
            return 0;
        }

        // 当前路径和
        currentSum += node.val;

        // 计算从当前路径和中减去目标值后，是否在前缀和中出现过
        int paths = prefixSumMap.getOrDefault(currentSum - target, 0);

        // 更新前缀和哈希表
        prefixSumMap.put(currentSum, prefixSumMap.getOrDefault(currentSum, 0) + 1);

        // 递归到左右子树
        paths += findPaths(node.left, target, currentSum);
        paths += findPaths(node.right, target, currentSum);

        // 递归结束后，回退前缀和哈希表，保证不影响其他路径
        prefixSumMap.put(currentSum, prefixSumMap.get(currentSum) - 1);

        return paths;
    }

    /**
     *
     *
     *        10
     *       /  \
     *      5    -3
     *     / \     \
     *    3   2     11
     *   / \   \
     *  3  -2   1
     *
     *
     * @param args
     */
    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(-3);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(2);
        root.left.left.left = new TreeNode(3);
        root.left.left.right = new TreeNode(-2);
        root.left.right.right = new TreeNode(1);
        root.right.right = new TreeNode(11);

        H437Leetcode h437Leetcode = new H437Leetcode();
        int i = h437Leetcode.pathSum(root, 8);
        System.out.println(i);

    }

}
